package nachos.threads;

import nachos.machine.*;

import java.util.TreeSet;
import java.util.HashSet;
import java.util.Iterator;

/**
 * A scheduler that chooses threads using a lottery.
 *
 * <p>
 * A lottery scheduler associates a number of tickets with each thread. When a
 * thread needs to be dequeued, a random lottery is held, among all the tickets
 * of all the threads waiting to be dequeued. The thread that holds the winning
 * ticket is chosen.
 *
 * <p>
 * Note that a lottery scheduler must be able to handle a lot of tickets
 * (sometimes billions), so it is not acceptable to maintain state for every
 * ticket.
 *
 * <p>
 * A lottery scheduler must partially solve the priority inversion problem; in
 * particular, tickets must be transferred through locks, and through joins.
 * Unlike a priority scheduler, these tickets add (as opposed to just taking
 * the maximum).
 */
public class LotteryScheduler extends PriorityScheduler {
    /**
     * Allocate a new lottery scheduler.
     */
    public static final int priorityMaximum = Integer.MAX_VALUE;
    public LotteryScheduler() {
    }
    
    /**
     * Allocate a new lottery thread queue.
     *
     * @param	transferPriority	<tt>true</tt> if this queue should
     *					transfer tickets from waiting threads
     *					to the owning thread.
     * @return	a new lottery thread queue.
     */
    public ThreadQueue newThreadQueue(boolean transferPriority) {
	return new LotteryQueue(transferPriority);
    }

    protected class LotteryQueue extends PriorityQueue {

        LotteryQueue(boolean transferPriority) {
            super(transferPriority);
        }

        public KThread nextThread() {
       
        ThreadState ts=pickNextThread();
        if(ts==null){
            return null;
        }
        KThread thread=ts.thread;
        queue.remove(thread);
        if(this.transferPriority && this.resourceHolder != null){
                // we reset the effective priority to the last resourceHolcer
                // because it doesn't need it anymore
                getThreadState(this.resourceHolder).resetEffectivePriority();
             }
            // we reset the queue asociated to the thread
            if(thread != null)
                getThreadState(thread).queue = null;
            this.resourceHolder = thread;
        return thread;

        }
        protected ThreadState pickNextThread(){

            int totalpriority=0;
            Iterator it=queue.iterator();
            while(it.hasNext()){
                totalpriority+=getThreadState(((KThread)it.next())).getEffectivePriority();
            }
            int goldenticket=(int)(Math.random()*totalpriority);
            it=queue.iterator();
            int suma=0;
            KThread elemento=null;
            while(it.hasNext()){
                elemento=((KThread)it.next());
                suma+=getThreadState(elemento).getEffectivePriority();
                if(suma>goldenticket){
                    break;
                }
            }

            if(elemento!=null){
                return getThreadState(elemento);
            }else{return null;}

        }
    }
}

